It is known to use a coding pattern to embed some type of information in a passive base such as a sheet of paper, a writing board or equivalent. A suitably programmed scanner, fax machine, camera or digital pen can then read, recreate and use the information embedded locally in the base. For example, graphical information on a base can be supplemented with embedded information which extends the functionality of the base. Such embedded information can comprise file data for full or partial recreation of the graphical information, commands, supplementary text or images, hyperlinks, absolute positions, etc.
Coding patterns are generally constructed around some form of machine-readable symbols or marks which are set out in relation to raster points of a regular, invisible raster on the base. Examples of such coding patterns are given in WO 00/73983, WO 01/26032, U.S. Pat. No. 5,477,012 and U.S. Pat. No. 5,221,833.
Generally, and in particular when the coding pattern is detected with a hand-held device such as a digital pen or scanner, the resulting image will contain, in addition to objects which correspond to the marks, also interference in the form of noise, geometric distortion, unevenness in signal level and/or sharpness, etc.
It is therefore generally a problem, before the decoding of the coding pattern, to be able to identify the symbols or marks in a way which is efficient in terms of computation and is not sensitive to interference.
The above problems and previously proposed solutions will be discussed below in connection with a special coding pattern which is described in detail in the above-mentioned patent publication WO 01/26032. The coding pattern consists of a raster and marks which are located at each raster point. The marks are preferably substantially round and are offset in relation to the raster points in any one of four orthogonal directions. The raster is virtual and is therefore invisible both to the eye and to sensors.
A coding pattern of the type in question can be used, for example, to code absolute positions on a base. This permits digital recording of information which is written and/or drawn by hand on the base with a digital pen. During the movement of the pen, images of the coding pattern are continually recorded locally at the pen point. A subset of objects in each of the images is decoded into a position. The decoded positions together constitute a digital description of the movement of the pen across the base.
Patent Publication WO 01/26034 describes an iterative technique for reconstruction of the virtual raster in a digital image of the above coding pattern. Each iteration involves the steps of identifying two adjoining objects; with knowledge of one object's location relative to its raster point and on the basis of a measured spacing between the objects, determining the raster point of the other object; and, starting at the raster point thus determined, looking for a new object within a search area which is defined with knowledge of the raster's nominal main directions. When all objects have been processed, one has worked through the image object by object and identified associated raster points and thereby reconstructed the virtual raster.
This technique is rapid, but it is relatively sensitive to interference because it is based on local decisions concerning individual objects and assessment of their positions relative to associated raster points.
An alternative technique is described in WO 01/75783. This uses Fourier analysis to extract direction vectors from a ensemble of points reflecting the location of the objects in the digital image. The overall main vectors of the ensemble of points are first determined, which main vectors are then used for correcting the ensemble of points with respect to rotation and scale errors in the image plane. Further main vectors in different parts of the corrected ensemble of points are thereafter computed in order to extract a measurement of perspective effects and phase shift. The ensemble of points is then finally corrected on the basis of these measurements, whereupon the virtual raster is given by the overall main vectors of the resulting ensemble of points. The technique is relatively insensitive to interference but in some circumstances it can be undesirably computation-intensive.